#include "common.h"
#include "base.h"
#include "scheduler.h"
#include <iostream>
#include <string>
#include <vector>
#include <ctime>
#include <cstdlib>

Scheduler::Scheduler(Configtable &config) {
    s_important_chances = std::vector<int>(config.get_snum(), config.get_max_percent_5());
    s_important_ttl = std::vector<int>(config.get_snum(), 0);
    line_cnt = 0;
}

void Scheduler::sort_c_info(std::vector<c_info> &c_info_list) {
    for (int i = 0; i < int(c_info_list.size()); i++) {
        c_info max = c_info_list[i];
        int index = i;
        for (int j = i + 1; j < int(c_info_list.size()); j++) {
            if (c_info_list[j].avg > max.avg) {
                max = c_info_list[j];
                index = j;
            }
        }
        c_info_list[index] = c_info_list[i];
        c_info_list[i] = max;
    }
}

#if METHOD == 1
void Scheduler::schedule(Configtable &config, demands &demands_in, allocs &allocs_out) {
    allocs_out.timestamp = demands_in.timestamp;
    int s_num = config.get_snum();
    int c_num = config.get_cnum();
    int sum_bw = 0;  // 总流量
    std::vector<int> pre_schedule(s_num, 0);  // 预分配列表
    std::vector<double> weight(s_num); // 权重列表
    std::vector<c_info> c_info_list(c_num);  // 需求详细信息列表

    // 初步计算客户需求信息并预分配
    for (int i = 0; i < int(demands_in.demand_list.size()); i++) {
        std::string cid = demands_in.demand_list[i].cid;
        c_info_list[i].cid = cid;
        int bw = demands_in.demand_list[i].bw;
        c_info_list[i].bw = bw;
        sum_bw += bw;
        for (int j = 0; j < s_num; j++) {
            if (config.check_qos(j, cid)) {
                c_info_list[i].aviliable.push_back(j);
            }
        }
        c_info_list[i].avg = bw / c_info_list[i].aviliable.size();
        c_info_list[i].rem = bw % c_info_list[i].aviliable.size();
        for (int j = 0; j < int(c_info_list[i].aviliable.size()); j++) {
            int s_index = c_info_list[i].aviliable[j];
            if (j == 0) {
                pre_schedule[s_index] += c_info_list[i].rem;
            }
            pre_schedule[s_index] += c_info_list[i].avg;
        }
    }

    // 计算拥堵权重
    for (int i = 0; i < int(pre_schedule.size()); i++) {
        if (pre_schedule[i] > 0) {
            weight[i] = double(sum_bw) / double(pre_schedule[i]);
        } else {
            weight[i] = -1;
        }
    }
    
    // 按照平均带宽需求排序
    sort_c_info(c_info_list);

    // 按照排序进行分配
    std::vector<int> app_schedule(s_num, 0);  // 分配列表

    for (int i = 0; i < int(c_info_list.size()); i++) {
        double sum_weight = 0;
        for (int j = 0; j < int(c_info_list[i].aviliable.size()); j++) {
            int s_index = c_info_list[i].aviliable[j];
            sum_weight += weight[s_index];
        }

        std::vector<int> c_alloc_bw(c_info_list[i].aviliable.size(), 0);
        int bw_sum = c_info_list[i].bw;
        int bw_app = 0;
        
        // 按权重分配
        for (int j = 0; j < int(c_info_list[i].aviliable.size()); j++) {
            int s_index = c_info_list[i].aviliable[j];
            int pre_bw = bw_sum * (weight[s_index] / sum_weight);
            if (bw_app + pre_bw > bw_sum) {
                pre_bw = bw_sum - bw_app;
            }
            if (!config.check_bandwidth(s_index, app_schedule[s_index] + pre_bw)) {
                pre_bw = config.get_bandwidth(s_index) - app_schedule[s_index];
            }
            app_schedule[s_index] += pre_bw;
            c_alloc_bw[j] += pre_bw;
            bw_app += pre_bw;
        }

        // 分配剩余
        int bw_left = (bw_sum - bw_app);
        for (int j = 0; j < int(c_info_list[i].aviliable.size()); j++) {
            if (bw_left == 0) {
                break;
            }
            int s_index = c_info_list[i].aviliable[j];
            int pre_bw = bw_left;
            if (!config.check_bandwidth(s_index, app_schedule[s_index] + pre_bw)) {
                pre_bw = config.get_bandwidth(s_index) - app_schedule[s_index];
                bw_left -= pre_bw;
            } else {
                bw_left = 0;
            }
            app_schedule[s_index] += pre_bw;
            c_alloc_bw[j] += pre_bw;
        }
        
        while (bw_left > 0) {} // 鸵鸟算法 骚凹瑞~

        c_alloc cur;
        cur.cid = c_info_list[i].cid;
        for (int j = 0; j < int(c_info_list[i].aviliable.size()); j++) {
            int s_index = c_info_list[i].aviliable[j];
            cur.s_alloc_list.push_back(s_alloc(config.get_sid(s_index), c_alloc_bw[j]));
            
        }
        

        allocs_out.c_alloc_list.push_back(cur);
    }

#ifdef DEBUG_SCHEDULER
    for (int i = 0; i < int(c_info_list.size()); i++) {
        std::cout << c_info_list[i].cid << "-" << c_info_list[i].avg << " ";
    }
    std::cout << std::endl;
    std::cout << "-----------------------------" << std::endl;
    for (int i = 0; i < int(pre_schedule.size()); i++) {
        std::cout << config.get_sid(i) << "-" << pre_schedule[i] << " ";
    }
    std::cout << std::endl;

    for (int i = 0; i < int(weight.size()); i++) {
        std::cout << config.get_sid(i) << "-" << weight[i] << " ";
    }
    std::cout << std::endl;

    int tmp = 0;
    for (int i = 0; i < int(app_schedule.size()); i++) {
        std::cout << config.get_sid(i) << "-" << app_schedule[i] << " ";
        tmp += app_schedule[i];
    }
    std::cout << std::endl;
    std::cout << tmp << " == " << sum_bw << std::endl;
#endif
}

#elif METHOD == 2
void Scheduler::schedule(Configtable &config, demands &demands_in, allocs &allocs_out) {
    allocs_out.timestamp = demands_in.timestamp;
    int s_num = config.get_snum();
    int c_num = config.get_cnum();
    int sum_bw = 0;  // 总流量
    std::vector<int> pre_schedule(s_num, 0);  // 预分配列表
    std::vector<double> weight(s_num); // 权重列表
    std::vector<c_info> c_info_list(c_num);  // 需求详细信息列表

    // 初步计算客户需求信息并预分配
    for (int i = 0; i < int(demands_in.demand_list.size()); i++) {
        std::string cid = demands_in.demand_list[i].cid;
        c_info_list[i].cid = cid;
        int bw = demands_in.demand_list[i].bw;
        c_info_list[i].bw = bw;
        sum_bw += bw;
        for (int j = 0; j < s_num; j++) {
            if (config.check_qos(j, cid)) {
                c_info_list[i].aviliable.push_back(j);
            }
        }
        c_info_list[i].avg = bw / c_info_list[i].aviliable.size();
        c_info_list[i].rem = bw % c_info_list[i].aviliable.size();
        for (int j = 0; j < int(c_info_list[i].aviliable.size()); j++) {
            int s_index = c_info_list[i].aviliable[j];
            if (j == 0) {
                pre_schedule[s_index] += c_info_list[i].rem;
            }
            pre_schedule[s_index] += c_info_list[i].avg;
        }
    }

    // 计算拥堵权重
    for (int i = 0; i < int(pre_schedule.size()); i++) {
        if (pre_schedule[i] > 0) {
            weight[i] = double(sum_bw) / double(pre_schedule[i]);
        } else {
            weight[i] = -1;
        }
    }
    
    // 按照平均带宽需求排序
    sort_c_info(c_info_list);

    // 按照排序进行分配
    std::vector<int> app_schedule(s_num, 0);  // 分配列表

    for (int i = 0; i < int(c_info_list.size()); i++) {
        double sum_weight = 0;
        for (int j = 0; j < int(c_info_list[i].aviliable.size()); j++) {
            int s_index = c_info_list[i].aviliable[j];
            sum_weight += weight[s_index];
        }

        std::vector<int> c_alloc_bw(c_info_list[i].aviliable.size(), 0);
        int bw_sum = c_info_list[i].bw;
        int bw_app = 0;
        
        // 按权重分配
        for (int j = 0; j < int(c_info_list[i].aviliable.size()); j++) {
            int s_index = c_info_list[i].aviliable[j];
            int pre_bw = bw_sum * (weight[s_index] / sum_weight);
            if (bw_app + pre_bw > bw_sum) {
                pre_bw = bw_sum - bw_app;
            }
            if (!config.check_bandwidth(s_index, app_schedule[s_index] + pre_bw)) {
                pre_bw = config.get_bandwidth(s_index) - app_schedule[s_index];
            }
            app_schedule[s_index] += pre_bw;
            c_alloc_bw[j] += pre_bw;
            bw_app += pre_bw;
        }

        int bw_left_sum = bw_sum - bw_app;
        int bw_left_app = 0;
        
        // 按权重分配剩余
        for (int j = 0; j < int(c_info_list[i].aviliable.size()); j++) {
            int s_index = c_info_list[i].aviliable[j];
            int pre_bw = bw_left_sum * (weight[s_index] / sum_weight);
            if (bw_left_app + pre_bw > bw_left_sum) {
                pre_bw = bw_left_sum - bw_left_app;
            }
            if (!config.check_bandwidth(s_index, app_schedule[s_index] + pre_bw)) {
                pre_bw = config.get_bandwidth(s_index) - app_schedule[s_index];
            }
            app_schedule[s_index] += pre_bw;
            c_alloc_bw[j] += pre_bw;
            bw_left_app += pre_bw;
        }

        // 分配剩余
        int bw_left = bw_left_sum - bw_left_app;
        for (int j = 0; j < int(c_info_list[i].aviliable.size()); j++) {
            if (bw_left == 0) {
                break;
            }
            int s_index = c_info_list[i].aviliable[j];
            int pre_bw = bw_left;
            if (!config.check_bandwidth(s_index, app_schedule[s_index] + pre_bw)) {
                pre_bw = config.get_bandwidth(s_index) - app_schedule[s_index];
                bw_left -= pre_bw;
            } else {
                bw_left = 0;
            }
            app_schedule[s_index] += pre_bw;
            c_alloc_bw[j] += pre_bw;
        }
        
        while (bw_left > 0) {} // 鸵鸟算法 骚凹瑞~

        c_alloc cur;
        cur.cid = c_info_list[i].cid;
        for (int j = 0; j < int(c_info_list[i].aviliable.size()); j++) {
            int s_index = c_info_list[i].aviliable[j];
            cur.s_alloc_list.push_back(s_alloc(config.get_sid(s_index), c_alloc_bw[j]));
            
        }
        

        allocs_out.c_alloc_list.push_back(cur);
    }

#ifdef DEBUG_SCHEDULER
    for (int i = 0; i < int(c_info_list.size()); i++) {
        std::cout << c_info_list[i].cid << "-" << c_info_list[i].avg << " ";
    }
    std::cout << std::endl;
    std::cout << "-----------------------------" << std::endl;
    for (int i = 0; i < int(pre_schedule.size()); i++) {
        std::cout << config.get_sid(i) << "-" << pre_schedule[i] << " ";
    }
    std::cout << std::endl;

    for (int i = 0; i < int(weight.size()); i++) {
        std::cout << config.get_sid(i) << "-" << weight[i] << " ";
    }
    std::cout << std::endl;

    int tmp = 0;
    for (int i = 0; i < int(app_schedule.size()); i++) {
        std::cout << config.get_sid(i) << "-" << app_schedule[i] << " ";
        tmp += app_schedule[i];
    }
    std::cout << std::endl;
    std::cout << tmp << " == " << sum_bw << std::endl;
#endif
}

#elif METHOD == 3
void Scheduler::schedule(Configtable &config, demands &demands_in, allocs &allocs_out) {
    allocs_out.timestamp = demands_in.timestamp;
    int s_num = config.get_snum();
    int c_num = config.get_cnum();
    int sum_bw = 0;  // 总流量
    std::vector<int> pre_schedule(s_num, 0);  // 预分配列表
    std::vector<double> weight(s_num); // 权重列表
    std::vector<c_info> c_info_list(c_num);  // 需求详细信息列表

    // 初步计算客户需求信息并预分配
    for (int i = 0; i < int(demands_in.demand_list.size()); i++) {
        std::string cid = demands_in.demand_list[i].cid;
        c_info_list[i].cid = cid;
        int bw = demands_in.demand_list[i].bw;
        c_info_list[i].bw = bw;
        sum_bw += bw;
        for (int j = 0; j < s_num; j++) {
            if (config.check_qos(j, cid)) {
                c_info_list[i].aviliable.push_back(j);
            }
        }
        c_info_list[i].avg = bw / c_info_list[i].aviliable.size();
        c_info_list[i].rem = bw % c_info_list[i].aviliable.size();
        for (int j = 0; j < int(c_info_list[i].aviliable.size()); j++) {
            int s_index = c_info_list[i].aviliable[j];
            if (j == 0) {
                pre_schedule[s_index] += c_info_list[i].rem;
            }
            pre_schedule[s_index] += c_info_list[i].avg;
        }
    }

    // 计算拥堵权重
    for (int i = 0; i < int(pre_schedule.size()); i++) {
        if (pre_schedule[i] > 0) {
            weight[i] = double(sum_bw) / double(pre_schedule[i]);
        } else {
            weight[i] = -1;
        }
    }
    
    // 按照平均带宽需求排序
    sort_c_info(c_info_list);

    // 按照排序进行分配
    std::vector<int> app_schedule(s_num, 0);  // 分配列表

    for (int i = 0; i < int(c_info_list.size()); i++) {
        double sum_weight = 0;
        for (int j = 0; j < int(c_info_list[i].aviliable.size()); j++) {
            int s_index = c_info_list[i].aviliable[j];
            sum_weight += weight[s_index];
        }

        std::vector<int> c_alloc_bw(c_info_list[i].aviliable.size(), 0);
        int bw_sum = c_info_list[i].bw;
        int bw_app = 0;
        
        // 按平均分配
        for (int j = 0; j < int(c_info_list[i].aviliable.size()); j++) {
            int s_index = c_info_list[i].aviliable[j];
            int pre_bw = c_info_list[i].avg;
            if (!config.check_bandwidth(s_index, app_schedule[s_index] + pre_bw)) {
                pre_bw = config.get_bandwidth(s_index) - app_schedule[s_index];
            }
            app_schedule[s_index] += pre_bw;
            c_alloc_bw[j] += pre_bw;
            bw_app += pre_bw;
        }

        int bw_left = (bw_sum - bw_app);
        for (int j = 0; j < int(c_info_list[i].aviliable.size()); j++) {
            if (bw_left == 0) {
                break;
            }
            int s_index = c_info_list[i].aviliable[j];
            int pre_bw = bw_left;
            if (!config.check_bandwidth(s_index, app_schedule[s_index] + pre_bw)) {
                pre_bw = config.get_bandwidth(s_index) - app_schedule[s_index];
                bw_left -= pre_bw;
            } else {
                bw_left = 0;
            }
            app_schedule[s_index] += pre_bw;
            c_alloc_bw[j] += pre_bw;
        }
        
        while (bw_left > 0) {} // 鸵鸟算法 骚凹瑞~

        c_alloc cur;
        cur.cid = c_info_list[i].cid;
        for (int j = 0; j < int(c_info_list[i].aviliable.size()); j++) {
            int s_index = c_info_list[i].aviliable[j];
            cur.s_alloc_list.push_back(s_alloc(config.get_sid(s_index), c_alloc_bw[j]));
            
        }
        

        allocs_out.c_alloc_list.push_back(cur);
    }

#ifdef DEBUG_SCHEDULER
    for (int i = 0; i < int(c_info_list.size()); i++) {
        std::cout << c_info_list[i].cid << "-" << c_info_list[i].avg << " ";
    }
    std::cout << std::endl;
    std::cout << "-----------------------------" << std::endl;
    for (int i = 0; i < int(pre_schedule.size()); i++) {
        std::cout << config.get_sid(i) << "-" << pre_schedule[i] << " ";
    }
    std::cout << std::endl;

    for (int i = 0; i < int(weight.size()); i++) {
        std::cout << config.get_sid(i) << "-" << weight[i] << " ";
    }
    std::cout << std::endl;

    int tmp = 0;
    for (int i = 0; i < int(app_schedule.size()); i++) {
        std::cout << config.get_sid(i) << "-" << app_schedule[i] << " ";
        tmp += app_schedule[i];
    }
    std::cout << std::endl;
    std::cout << tmp << " == " << sum_bw << std::endl;
#endif
}

#elif METHOD == 4
void Scheduler::schedule(Configtable &config, demands &demands_in, allocs &allocs_out) {
    int s_num = config.get_snum();
    int c_num = config.get_cnum();
    int sum_bw = 0;  // 总流量
    std::vector<int> pre_schedule(s_num, 0);  // 预分配列表
    std::vector<double> weight(s_num); // 权重列表
    std::vector<c_info> c_info_list(c_num);  // 需求详细信息列表

    // 初步计算客户需求信息并预分配所有请求
    for (int i = 0; i < int(demands_in.demand_list.size()); i++) {
        std::string cid = demands_in.demand_list[i].cid;
        c_info_list[i].cid = cid;
        int bw = demands_in.demand_list[i].bw;
        c_info_list[i].bw = bw;
        sum_bw += bw;
        for (int j = 0; j < s_num; j++) {
            if (config.check_qos(j, cid)) {
                c_info_list[i].aviliable.push_back(j);
            }
        }
        c_info_list[i].avg = bw / c_info_list[i].aviliable.size();
        c_info_list[i].rem = bw % c_info_list[i].aviliable.size();
        for (int j = 0; j < int(c_info_list[i].aviliable.size()); j++) {
            int s_index = c_info_list[i].aviliable[j];
            pre_schedule[s_index] += c_info_list[i].bw;
        }
    }

    // 客户需求排序
    sort_c_info(c_info_list);

    // 初始化分配表
    allocs_out.timestamp = demands_in.timestamp;

    // 分配列表
    std::vector<int> app_schedule(s_num, 0);
    // 每个客户的具体分配列表
    std::vector<std::vector<int>> app_every_schedule(c_num, std::vector<int>(s_num, 0));

    // 寻找担当节点
    int important_s_index = -1;
    int max_bw = -1;
    double ratio = -1;
    if (config.check_max_percent_5_flag(line_cnt)) {
        for (int i = 0; i < s_num; i++) {
            int max_bw_cur = pre_schedule[i];
            double ratio_cur = 1.0;
            if (!config.check_bandwidth(i, max_bw_cur)) {
                ratio_cur = (double)(config.get_bandwidth(i)) / (double)(max_bw_cur);
                max_bw_cur = config.get_bandwidth(i);
            }
            if (max_bw_cur > max_bw && s_important_chances[i] > 0) {
                important_s_index = i;
                max_bw = max_bw_cur;
                ratio = ratio_cur;
            }
        }
        if (important_s_index != -1) {
            s_important_chances[important_s_index]--;
            for (int i = 0; i < int(c_info_list.size()); i++) {
                for (int j = 0; j < int(c_info_list[i].aviliable.size()); j++) {
                    int s_index = c_info_list[i].aviliable[j];
                    if (s_index == important_s_index) {
                        int pre_bw = c_info_list[i].bw * ratio;
                        if (!config.check_bandwidth(s_index, app_schedule[s_index] + pre_bw)) {
                            pre_bw = config.get_bandwidth(s_index) - app_schedule[s_index];
                        }
                        app_schedule[s_index] += pre_bw;
                        app_every_schedule[i][s_index] += pre_bw;
                        c_info_list[i].bw -= pre_bw;
                        c_info_list[i].avg = c_info_list[i].bw / (c_info_list[i].aviliable.size() - 1);
                        c_info_list[i].rem = c_info_list[i].bw % (c_info_list[i].aviliable.size() - 1);
                    }
                }
            }
        }
    }

    // 开始平均其他节点，预分配
    pre_schedule = std::vector<int>(s_num, 0);
    for (int i = 0; i < int(demands_in.demand_list.size()); i++) {
        for (int j = 0; j < int(c_info_list[i].aviliable.size()); j++) {
            int s_index = c_info_list[i].aviliable[j];
            if (s_index != important_s_index) {
                pre_schedule[s_index] += c_info_list[i].avg;
            }
        }
    }


    // 计算拥堵权重
    for (int i = 0; i < int(pre_schedule.size()); i++) {
        if (pre_schedule[i] > 0) {
            weight[i] = double(sum_bw) / double(pre_schedule[i]);
        } else {
            weight[i] = 0;
        }
    }
    


    for (int i = 0; i < int(c_info_list.size()); i++) {
        double sum_weight = 0;
        for (int j = 0; j < int(c_info_list[i].aviliable.size()); j++) {
            int s_index = c_info_list[i].aviliable[j];
            sum_weight += weight[s_index];
        }

        int bw_sum = c_info_list[i].bw;
        int bw_app = 0;
        
        // 按权重分配
        for (int j = 0; j < int(c_info_list[i].aviliable.size()); j++) {
            int s_index = c_info_list[i].aviliable[j];
            if (s_index != important_s_index) {
                int pre_bw = bw_sum * (weight[s_index] / sum_weight);
                if (bw_app + pre_bw > bw_sum) {
                    pre_bw = bw_sum - bw_app;
                }
                if (!config.check_bandwidth(s_index, app_schedule[s_index] + pre_bw)) {
                    pre_bw = config.get_bandwidth(s_index) - app_schedule[s_index];
                }
                app_schedule[s_index] += pre_bw;
                app_every_schedule[i][s_index] += pre_bw;
                bw_app += pre_bw;
            }
        }

        // 分配剩余
        int bw_left = (bw_sum - bw_app);
        for (int j = 0; j < int(c_info_list[i].aviliable.size()); j++) {
            if (bw_left == 0) {
                break;
            }
            int s_index = c_info_list[i].aviliable[j];
            if (s_index != important_s_index) {
                int pre_bw = bw_left;
                if (!config.check_bandwidth(s_index, app_schedule[s_index] + pre_bw)) {
                    pre_bw = config.get_bandwidth(s_index) - app_schedule[s_index];
                    bw_left -= pre_bw;
                } else {
                    bw_left = 0;
                }
                app_schedule[s_index] += pre_bw;
                app_every_schedule[i][s_index] += pre_bw;
            }
        }
        
        c_alloc cur;
        cur.cid = c_info_list[i].cid;
        for (int j = 0; j < int(c_info_list[i].aviliable.size()); j++) {
            int s_index = c_info_list[i].aviliable[j];
            if (app_every_schedule[i][s_index] > 0) {
                cur.s_alloc_list.push_back(s_alloc(config.get_sid(s_index), app_every_schedule[i][s_index]));
            }
        }

        allocs_out.c_alloc_list.push_back(cur);
    }

    line_cnt++;


#ifdef DEBUG_SCHEDULER
    for (int i = 0; i < int(s_important_chances.size()); i++) {
        std::cout << s_important_chances[i] << " ";
    }
    std::cout << "----------------------------" << std::endl;
    for (int i = 0; i < int(c_info_list.size()); i++) {
        std::cout << c_info_list[i].cid << "-" << c_info_list[i].avg << " ";
    }
    std::cout << std::endl;
    std::cout << "-----------------------------" << std::endl;
    for (int i = 0; i < int(pre_schedule.size()); i++) {
        std::cout << config.get_sid(i) << "-" << pre_schedule[i] << " ";
    }
    std::cout << std::endl;

    for (int i = 0; i < int(weight.size()); i++) {
        std::cout << config.get_sid(i) << "-" << weight[i] << " ";
    }
    std::cout << std::endl;

    int tmp = 0;
    for (int i = 0; i < int(app_schedule.size()); i++) {
        std::cout << config.get_sid(i) << "-" << app_schedule[i] << " ";
        tmp += app_schedule[i];
    }
    std::cout << std::endl;
    std::cout << tmp << " == " << sum_bw << std::endl;
#endif
}

#elif METHOD == 5
void Scheduler::schedule(Configtable &config, demands &demands_in, allocs &allocs_out) {
    int s_num = config.get_snum();
    int c_num = config.get_cnum();
    int sum_bw = 0;  // 总流量
    std::vector<int> pre_schedule(s_num, 0);  // 预分配列表
    std::vector<double> weight(s_num); // 权重列表
    std::vector<c_info> c_info_list(c_num);  // 需求详细信息列表

    // 初步计算客户需求信息并预分配所有请求
    for (int i = 0; i < int(demands_in.demand_list.size()); i++) {
        std::string cid = demands_in.demand_list[i].cid;
        c_info_list[i].cid = cid;
        int bw = demands_in.demand_list[i].bw;
        c_info_list[i].bw = bw;
        sum_bw += bw;
        for (int j = 0; j < s_num; j++) {
            if (config.check_qos(j, cid)) {
                c_info_list[i].aviliable.push_back(j);
            }
        }
        c_info_list[i].avg = bw / c_info_list[i].aviliable.size();
        c_info_list[i].rem = bw % c_info_list[i].aviliable.size();
    }

    // 客户需求排序
    sort_c_info(c_info_list);
    // 主节点列表
    std::vector<int> important_s_index(c_num, 0);
    for (int i = 0; i < int(c_info_list.size()); i++) {
        int important_s = -1;
        int important_s_qos = 500;
        for (int j = 0; j < int(c_info_list[i].aviliable.size()); j++) {
            // if (config.get_bandwidth(c_info_list[i].aviliable[j]) > important_s_bw) {
            //     important_s = c_info_list[i].aviliable[j];
            //     important_s_bw = config.get_bandwidth(c_info_list[i].aviliable[j]);
            // }
            if (config.get_qos(c_info_list[i].aviliable[j], c_info_list[i].cid) < important_s_qos) {
                important_s = c_info_list[i].aviliable[j];
                important_s_qos = config.get_qos(c_info_list[i].aviliable[j], c_info_list[i].cid);
            }
        }
        important_s_index[i] = important_s;
    }



    // 初始化分配表
    allocs_out.timestamp = demands_in.timestamp;

    // 分配列表
    std::vector<int> app_schedule(s_num, 0);
    // 每个客户的具体分配列表
    std::vector<std::vector<int>> app_every_schedule(c_num, std::vector<int>(s_num, 0));

    // 主节点分配
    double ratio = 0.6;
    for (int i = 0; i < int(c_info_list.size()); i++) {
        int s_index = important_s_index[i];
        int pre_bw = c_info_list[i].bw * ratio;
        if (!config.check_bandwidth(s_index, app_schedule[s_index] + pre_bw)) {
            pre_bw = config.get_bandwidth(s_index) - app_schedule[s_index];
        }
        app_schedule[s_index] += pre_bw;
        app_every_schedule[i][s_index] += pre_bw;
        c_info_list[i].bw -= pre_bw;
        c_info_list[i].avg = c_info_list[i].bw / c_info_list[i].aviliable.size();
        c_info_list[i].rem = c_info_list[i].bw % c_info_list[i].aviliable.size();
        
    }

    // 开始平均其他节点，预分配
    for (int i = 0; i < int(demands_in.demand_list.size()); i++) {
        for (int j = 0; j < int(c_info_list[i].aviliable.size()); j++) {
            int s_index = c_info_list[i].aviliable[j];
            pre_schedule[s_index] += c_info_list[i].avg;
        }
    }


    // 计算拥堵权重
    for (int i = 0; i < int(pre_schedule.size()); i++) {
        if (pre_schedule[i] > 0) {
            weight[i] = double(sum_bw) / double(pre_schedule[i]);
        } else {
            weight[i] = 0;
        }
    }
    


    for (int i = 0; i < int(c_info_list.size()); i++) {
        double sum_weight = 0;
        for (int j = 0; j < int(c_info_list[i].aviliable.size()); j++) {
            int s_index = c_info_list[i].aviliable[j];
            sum_weight += weight[s_index];
        }

        int bw_sum = c_info_list[i].bw;
        int bw_app = 0;
        
        // 按权重分配
        for (int j = 0; j < int(c_info_list[i].aviliable.size()); j++) {
            int s_index = c_info_list[i].aviliable[j];
            int pre_bw = bw_sum * (weight[s_index] / sum_weight);
            if (bw_app + pre_bw > bw_sum) {
                pre_bw = bw_sum - bw_app;
            }
            if (!config.check_bandwidth(s_index, app_schedule[s_index] + pre_bw)) {
                pre_bw = config.get_bandwidth(s_index) - app_schedule[s_index];
            }
            app_schedule[s_index] += pre_bw;
            app_every_schedule[i][s_index] += pre_bw;
            bw_app += pre_bw;
        }

        // 分配剩余
        int bw_left = (bw_sum - bw_app);
        for (int j = 0; j < int(c_info_list[i].aviliable.size()); j++) {
            if (bw_left == 0) {
                break;
            }
            int s_index = c_info_list[i].aviliable[j];
            int pre_bw = bw_left;
            if (!config.check_bandwidth(s_index, app_schedule[s_index] + pre_bw)) {
                pre_bw = config.get_bandwidth(s_index) - app_schedule[s_index];
                bw_left -= pre_bw;
            } else {
                bw_left = 0;
            }
            app_schedule[s_index] += pre_bw;
            app_every_schedule[i][s_index] += pre_bw;
        }

        
        c_alloc cur;
        cur.cid = c_info_list[i].cid;
        for (int j = 0; j < int(c_info_list[i].aviliable.size()); j++) {
            int s_index = c_info_list[i].aviliable[j];
            if (app_every_schedule[i][s_index] > 0) {
                cur.s_alloc_list.push_back(s_alloc(config.get_sid(s_index), app_every_schedule[i][s_index]));
            }
        }

        allocs_out.c_alloc_list.push_back(cur);
    }

    line_cnt++;


#ifdef DEBUG_SCHEDULER
    for (int i = 0; i < int(s_important_chances.size()); i++) {
        std::cout << s_important_chances[i] << " ";
    }
    std::cout << "----------------------------" << std::endl;
    for (int i = 0; i < int(c_info_list.size()); i++) {
        std::cout << c_info_list[i].cid << "-" << c_info_list[i].avg << " ";
    }
    std::cout << std::endl;
    std::cout << "-----------------------------" << std::endl;
    for (int i = 0; i < int(pre_schedule.size()); i++) {
        std::cout << config.get_sid(i) << "-" << pre_schedule[i] << " ";
    }
    std::cout << std::endl;

    for (int i = 0; i < int(weight.size()); i++) {
        std::cout << config.get_sid(i) << "-" << weight[i] << " ";
    }
    std::cout << std::endl;

    int tmp = 0;
    for (int i = 0; i < int(app_schedule.size()); i++) {
        std::cout << config.get_sid(i) << "-" << app_schedule[i] << " ";
        tmp += app_schedule[i];
    }
    std::cout << std::endl;
    std::cout << tmp << " == " << sum_bw << std::endl;
#endif
}
#elif METHOD == 6
void Scheduler::schedule(Configtable &config, demands &demands_in, allocs &allocs_out) {
    int s_num = config.get_snum();
    int c_num = config.get_cnum();
    int sum_bw = 0;  // 总流量
    std::vector<int> pre_schedule;  // 预分配列表
    std::vector<double> weight(s_num); // 权重列表
    std::vector<c_info> c_info_list(c_num);  // 需求详细信息列表

    // 初步计算客户需求信息并预分配所有请求
    for (int i = 0; i < int(demands_in.demand_list.size()); i++) {
        std::string cid = demands_in.demand_list[i].cid;
        c_info_list[i].cid = cid;
        int bw = demands_in.demand_list[i].bw;
        c_info_list[i].bw = bw;
        sum_bw += bw;
        for (int j = 0; j < s_num; j++) {
            if (config.check_qos(j, cid)) {
                c_info_list[i].aviliable.push_back(j);
            }
        }
        c_info_list[i].avi_num = c_info_list[i].aviliable.size();
        c_info_list[i].avg = bw / c_info_list[i].aviliable.size();
        c_info_list[i].rem = bw % c_info_list[i].aviliable.size();
    }

    // 客户需求排序
    sort_c_info(c_info_list);

    // 初始化分配表
    allocs_out.timestamp = demands_in.timestamp;

    // 分配列表
    std::vector<int> app_schedule(s_num, 0);
    // 每个客户的具体分配列表
    std::vector<std::vector<int>> app_every_schedule(c_num, std::vector<int>(s_num, 0));

    // 寻找担当节点
    std::vector<int> important_s_index_list;
    while (true) {
        pre_schedule = std::vector<int>(s_num, 0);
        for (int i = 0; i < int(c_info_list.size()); i++) {
            for (int j = 0; j < int(c_info_list[i].aviliable.size()); j++) {
                int s_index = c_info_list[i].aviliable[j];
                int is_exist = 0;
                for (int k = 0; k < int(important_s_index_list.size()); k++) {
                    if (important_s_index_list[k] == s_index) {
                        is_exist = 1;
                        break;
                    }
                }
                if (is_exist == 0) {
                    pre_schedule[s_index] += c_info_list[i].bw;
                }
            }
        }
        int important_s_index = -1;
        double ratio = -1;
        double ratio_for_ratio = 0.7;
        int max_ttl = -1;
        // 0.95 1137401
        // 0.91 1119740
        // 0.9 1087816
        // 0.8 1002371
        // 0.7 877880
        // 0.6 802298
        // 0.5 697912
        // 0.4 668605
        // 0.2 1448430

        // 正式赛
        // 0.4 6291965
        // 0.2 6224386
        // 0.6 4435645
        // 0.8 3827139
        // 0.9 4071530
        // 0.85 3996736
        // 0.82 3840878
        // 0.7 4004133

        // ttl
        // 0.8 3869796
        // 0.78 3821911
        // 0.76 3803848
        // 0.72 3740656
        // 0.7 3719506
        std::vector<double> max_percent_5_ratio = config.get_max_percent_5_ratio();

        // srand(time(0));
        // int b_i = rand();
        std::vector<int> degree_sort = config.get_degree_sort();
        for (int cnt = 0; cnt < s_num; cnt++) {
            // int i = (b_i + cnt) % s_num;
            int i = degree_sort[cnt];
            int max_bw_cur = pre_schedule[i];
            // double max_bw_ratio = max_percent_5_ratio[i];
            double max_bw_ratio = max_percent_5_ratio[i] * ratio_for_ratio;
            if (max_bw_cur > max_bw_ratio * config.get_bandwidth(i) && s_important_chances[i] > 0 && s_important_ttl[i] > max_ttl) {
                double ratio_cur = 1.0;
                if (!config.check_bandwidth(i, max_bw_cur)) {
                    ratio_cur = (double)(config.get_bandwidth(i)) / (double)(max_bw_cur);
                }
                important_s_index = i;
                ratio = ratio_cur;
                max_ttl = s_important_ttl[i];
                // break;
            }
        }
        if (important_s_index != -1) {
            s_important_chances[important_s_index]--;
            important_s_index_list.push_back(important_s_index);
            for (int i = 0; i < int(c_info_list.size()); i++) {
                for (int j = 0; j < int(c_info_list[i].aviliable.size()); j++) {
                    int s_index = c_info_list[i].aviliable[j];
                    if (s_index == important_s_index) {
                        int pre_bw = c_info_list[i].bw * ratio;
                        if (!config.check_bandwidth(s_index, app_schedule[s_index] + pre_bw)) {
                            pre_bw = config.get_bandwidth(s_index) - app_schedule[s_index];
                        }
                        app_schedule[s_index] += pre_bw;
                        app_every_schedule[i][s_index] += pre_bw;
                        c_info_list[i].bw -= pre_bw;
                        c_info_list[i].avi_num--;
                        if (c_info_list[i].avi_num > 0) {
                            c_info_list[i].avg = c_info_list[i].bw / c_info_list[i].avi_num;
                            c_info_list[i].rem = c_info_list[i].bw % c_info_list[i].avi_num;
                        } else {
                            c_info_list[i].avg = 0;
                            c_info_list[i].rem = 0;
                        }
                    }
                }
            }
        } else {
            break;
        }
    }
    for (int i = 0; i < s_num; i++) {
        s_important_ttl[i]++;
    }
    for (int i = 0; i < int(important_s_index_list.size()); i++) {
        int index = important_s_index_list[i];
        s_important_ttl[index] = 0;
    }

    // 开始平均其他节点，预分配
    pre_schedule = std::vector<int>(s_num, 0);
    for (int i = 0; i < int(demands_in.demand_list.size()); i++) {
        for (int j = 0; j < int(c_info_list[i].aviliable.size()); j++) {
            int s_index = c_info_list[i].aviliable[j];
            int is_exist = 0;
            for (int k = 0; k < int(important_s_index_list.size()); k++) {
                if (important_s_index_list[k] == s_index) {
                    is_exist = 1;
                    break;
                }
            }
            if (is_exist == 0) {
                pre_schedule[s_index] += c_info_list[i].avg;
            }
        }
    }

    // 计算拥堵权重
    for (int i = 0; i < int(pre_schedule.size()); i++) {
        if (pre_schedule[i] > 0) {
            weight[i] = double(sum_bw) / double(pre_schedule[i]);
        } else {
            weight[i] = 0;
        }
    }

    for (int i = 0; i < int(c_info_list.size()); i++) {
        double sum_weight = 0;
        for (int j = 0; j < int(c_info_list[i].aviliable.size()); j++) {
            int s_index = c_info_list[i].aviliable[j];
            sum_weight += weight[s_index];
        }

        int bw_sum = c_info_list[i].bw;
        int bw_app = 0;
        
        // 按权重分配
        for (int j = 0; j < int(c_info_list[i].aviliable.size()); j++) {
            int s_index = c_info_list[i].aviliable[j];
            int is_exist = 0;
            for (int k = 0; k < int(important_s_index_list.size()); k++) {
                if (important_s_index_list[k] == s_index) {
                    is_exist = 1;
                    break;
                }
            }
            if (is_exist == 0) {
                int pre_bw = bw_sum * (weight[s_index] / sum_weight);
                if (bw_app + pre_bw > bw_sum) {
                    pre_bw = bw_sum - bw_app;
                }
                if (!config.check_bandwidth(s_index, app_schedule[s_index] + pre_bw)) {
                    pre_bw = config.get_bandwidth(s_index) - app_schedule[s_index];
                }
                app_schedule[s_index] += pre_bw;
                app_every_schedule[i][s_index] += pre_bw;
                bw_app += pre_bw;
            }
        }

        // 分配剩余
        int bw_left = (bw_sum - bw_app);
        for (int j = 0; j < int(c_info_list[i].aviliable.size()); j++) {
            if (bw_left == 0) {
                break;
            }
            int s_index = c_info_list[i].aviliable[j];
            int is_exist = 0;
            for (int k = 0; k < int(important_s_index_list.size()); k++) {
                if (important_s_index_list[k] == s_index) {
                    is_exist = 1;
                    break;
                }
            }
            if (is_exist == 0) {
                int pre_bw = bw_left;
                if (!config.check_bandwidth(s_index, app_schedule[s_index] + pre_bw)) {
                    pre_bw = config.get_bandwidth(s_index) - app_schedule[s_index];
                    bw_left -= pre_bw;
                } else {
                    bw_left = 0;
                }
                app_schedule[s_index] += pre_bw;
                app_every_schedule[i][s_index] += pre_bw;
            }
        }
        
        c_alloc cur;
        cur.cid = c_info_list[i].cid;
        for (int j = 0; j < int(c_info_list[i].aviliable.size()); j++) {
            int s_index = c_info_list[i].aviliable[j];
            if (app_every_schedule[i][s_index] > 0) {
                cur.s_alloc_list.push_back(s_alloc(config.get_sid(s_index), app_every_schedule[i][s_index]));
            }
        }

        allocs_out.c_alloc_list.push_back(cur);
    }
#ifdef DEBUG_SCHEDULER
    for (int i = 0; i < int(s_important_chances.size()); i++) {
        std::cout << s_important_chances[i] << " ";
    }
    std::cout << "----------------------------" << std::endl;
    for (int i = 0; i < int(c_info_list.size()); i++) {
        std::cout << c_info_list[i].cid << "-" << c_info_list[i].avg << " ";
    }
    std::cout << std::endl;
    std::cout << "-----------------------------" << std::endl;
    for (int i = 0; i < int(pre_schedule.size()); i++) {
        std::cout << config.get_sid(i) << "-" << pre_schedule[i] << " ";
    }
    std::cout << std::endl;

    for (int i = 0; i < int(weight.size()); i++) {
        std::cout << config.get_sid(i) << "-" << weight[i] << " ";
    }
    std::cout << std::endl;

    int tmp = 0;
    for (int i = 0; i < int(app_schedule.size()); i++) {
        std::cout << config.get_sid(i) << "-" << app_schedule[i] << " ";
        tmp += app_schedule[i];
    }
    std::cout << std::endl;
    std::cout << tmp << " == " << sum_bw << std::endl;
#endif
}

#endif

Scheduler::~Scheduler() {
    
}
